package com.shr.code_interview;

public class Solution_51 {
	
	public static int count;
    public int InversePairs(int [] array) {
    	count = 0;
    	int[] auxArray = new int[array.length] ;
        mergeSort(array, 0 , array.length - 1, auxArray);
        return count ;
    }

	private void mergeSort(int[] array, int low, int up, int[] auxArray) {
		if(low < up){
			int mid = (low + up) / 2 ;
			mergeSort(array, low, mid , auxArray);
			mergeSort(array, mid + 1, up, auxArray) ;
			
			for(int i = low;i<=up;i++){
				auxArray[i] = array[i] ;
			}
			
			//原地归并
			int t = up, hi = up, lo = mid;
			for(int i = low;i <= up;i++){
				if(lo < low) array[t--] = auxArray[hi--];
				else if(hi < mid + 1) array[t--] = auxArray[lo--];
				else if(auxArray[lo] > auxArray[hi]){
					array[t--] = auxArray[lo--] ;
					count += (hi - mid) ;
					count %= 1000000007 ;
				}else array[t--] = auxArray[hi--] ;
			}
		}
	}
}
